/*
 * @lc app=leetcode id=77 lang=cpp
 *
 * [77] Combinations
 */
class Solution {
public:
    vector<vector<int>> combine(int n, int k) {
        vector<vector<int>> ret;
        if (n < k) {
            return ret;
        }
        vector<int> v;
        loop(n, k, 0, v, ret);
        return ret;
    }

    void loop(int n, int k, int idx, vector<int>& v, vector<vector<int>>& ret) {
       
        if (k == 0) {
            ret.push_back(v);
            return ;
        }

        if (k + idx > n) {
            return ;
        }
 
        v.push_back(idx+1);
        loop(n, k-1, idx+1, v, ret);
        v.pop_back();
        loop(n, k, idx+1, v, ret);
    }

};

